package main.java.utils.hxy.tree;

/**
 * 左边小 右边大
 */
public class BinarySearchTree implements  Tree {
    //根节点
    private Node root;
    @Override
    public boolean insert(int data) {
        Node newNode = new Node(data);
        //判断root节点是否为空
        if(root == null){
            root = newNode;
            return true;
        }else {
            Node current = root;
            Node parentNode;
            while (current != null){
                parentNode = current;
                //节点的值比新节点的值小 那么新节点在左边
                if(current.data < data){
                    current = current.left;
                    if(current == null){
                        parentNode.left = newNode;
                        return true;
                    }
                }else {
                    current = current.right;
                    if(current == null)
                        parentNode.right = newNode;
                        return true;
                }
            }
        }
        return false;
    }



    @Override
    public Node find(int key) {
        Node current = root;
        while (current != null){
            if(current.data > key){
                current = current.left;
            }else if (current.data < key){
                current = current.right;
            }else{
                return current;
            }
        }
        return null;
    }

    @Override
    public boolean delete(int key) {
        //0 个节点 1个节点 2个节点
        Node curr = root;
        Node parentNode=null;
        boolean isLeftChild = false;
        while(curr.data != key){
            parentNode = curr;
            if(curr.data > key){
                curr = curr.left;
                isLeftChild = true;
            }else{
                curr = curr.right;
            }
        }
        if(curr.left == null && curr.right == null){
            if(isLeftChild){
                parentNode.left = null;
                return true;
            }else{
                parentNode.right = null;
                return true;
            }
        }
        if(curr.left == null && curr.right != null){
            if(curr == root){
                curr = curr.right;
            }else if(isLeftChild){
                parentNode.left = curr.right;
            }else{
                parentNode.right = curr.right;
            }
            return true;
        }
        if(curr.left != null && curr.right == null){
            if(curr == root){
                curr = curr.left;
            }else if(isLeftChild){
                parentNode.left = curr.left;
            }else{
                parentNode.right = curr.left;
            }
            return true;
        }
        if(curr.left != null && curr.right != null){
            Node successor = findSuccessor(curr);
            if(curr == root){
                this.root = successor;
            }else if(isLeftChild){
                parentNode.left = successor;
            }else{
                parentNode.right = successor;
            }
            successor.left = curr.left;
        }
        return false;
    }

    /**
     * 删除节点的右子树的最小节点
     * 找到右边的最小节点后 把 这个节点的右子树替换成删除节点的右子树
     * 左子树替换成删除节点的左子树 这个节点的父节点的左子树替换掉
     * @param delNode
     */
    private Node findSuccessor(Node delNode) {
        Node delParentNode = delNode;
        Node currNode = delNode.right;
        Node success = delNode;
        while(currNode != null){
            delParentNode = delNode;
            success = currNode;
            currNode = currNode.left;
        }
        if(success != delNode.right){
            delParentNode.left = delNode.right;
            success.right = delNode.right;
        }

        return success;
    }

    @Override
    public Node findMax() {
        Node curr = root;
        Node maxNode = curr;
        while(curr != null){
            maxNode = curr;
            curr = curr.right;
        }
        return maxNode;
    }

    @Override
    public Node findMin() {
        Node curr = root;
        Node minNode = curr;
        while(curr != null){
            minNode = curr;
            curr = curr.left;
        }
        return minNode;
    }

    @Override
    public void infixOrder(Node current) {
        while (current != null){
            System.out.print(current.data);
            infixOrder(current.left);
            infixOrder(current.right);
        }
    }

    @Override
    public void preOrder(Node current) {

    }

    @Override
    public void postOrder(Node current) {

    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public int height() {
        return 0;
    }

    public void clear() {
        root =null;
    }
}
